1321. Счастливые пятерки

Сосновый бор. Мачтовый лес в Вятской губернии. 1872. Крамской, друг художника, писал о «Сосновом боре», подчеркивая натурную достоверность изображенного: «Лес глухой и ручей с железистой, темно-желтой водой, в котором видно все дно, усеянное камнями...» Однако необходимо отметить, что Шишкин на своем полотне несколько театрализует лесной пейзаж, предлагая «природный спектакль».

Некоторые люди считают пятерку счастливым числом. Они бросают несколько костей, и если пятерка выпадает больше чем в одной пятой части костей, то день считается счастливым.

Бросается dice одинаковых костей, имеющих sides сторон. Необходимо вычислить вероятность того, что день будет счастливым. Вероятность выпадения пятерки при бросании кости с sides сторонами равна 1 / sides.

Вход. Каждая строка является отдельным тестом и содержит количество бросаемых костей dice (1 £ dice £ 20) и количество сторон sides (5 £ sides £ 10) в них.

Выход. Для каждого теста в отдельной строке вывести вероятность того, что день будет счастливым. Вероятность выводить с 6 знаками после десятичной запятой.

Пример входа

1 6

5 6

20 10

1 10

Пример выхода

0.166667

0.196245

0.043174

0.100000

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

.Заведем двумерный массив p[21][21], в котором p[d][i] равно вероятности выпадения в точности i пятерок при бросании d костей. Занесем в переменную q вероятность выпадения пятерки на кости, состоящей из sides сторон. Изначально обнулим массив p, присвоим p[0][0] = 1 (вероятность выпадения 0 пятерок при бросании 0 костей равна 1).

При бросании d костей выпадет в точности i пятерок, если:

а) после бросания d – 1 кости выпало i пятерок, а на d - ой кости выпала не пятерка. Вероятность этого события равна p[d – 1][i] * (1 – q).

б) после бросания d – 1 кости выпала i – 1 пятерка, а на d - ой кости выпала пятерка. Вероятность этого события равна p[d – 1][i – 1] * q.

Таким образом,

p[d][i] = p[d – 1][i] * (1 – q) + p[d – 1][i – 1] * q

Пересчитаем по этой формуле все значения p[d][i], 1 £ d £ dice, 0 £ i £ dice. День считается удачным, если пятерка выпадет как минимум на dice / 5 + 1 кости (больше чем в одной пятой части). Для нахождения требуемой вероятности остается просуммировать значения p[dice][i] для i от dice / 5 + 1 до dice.